package cy1;

public class Solution {
    static class Node {
        int val = 0;
        Node left = null;
        Node right = null;

        public Node(int val) {
            this.val = val;
        }
    }

    static Node prev = null;

    public static Node Convert(Node root) {
        if (root == null) {
            return null;
        }
        convertToList(root);
        Node cur=root;
        Node leftto=root;
        Node rightto=root;;
        while(leftto.left!=null){
            leftto=leftto.left;
        }
        while(rightto.right!=null){
            rightto=rightto.right;
        }
        leftto.left=rightto;
        rightto.right=leftto;
        return leftto;
    }

    public static void convertToList(Node root) {
        if (root == null) {
            return;
        }
        Node cur = root;
        convertToList(cur.left);
        cur.left = prev;
        if (prev != null) {
            prev.right = cur;
        }
        prev = cur;
        convertToList(cur.right);
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node2.left = node1;
        node2.right = node3;

        Solution.Convert(node2);
        System.out.println();

    }

}
